package bch.maven.plugin.util;

import com.google.common.graph.Graph;
import java.util.*;

public class GuavaGraphUtils {

    /**
     * 检查有向图是否存在环路（DFS）
     */
    public static <T> boolean hasCycle(Graph<T> graph) {
        Set<T> visited = new HashSet<>();
        Set<T> stack = new HashSet<>();
        for (T node : graph.nodes()) {
            if (dfs(node, graph, visited, stack)) {
                return true;
            }
        }
        return false;
    }

    private static <T> boolean dfs(T node, Graph<T> graph, Set<T> visited, Set<T> stack) {
        if (stack.contains(node)) return true; // 检测到回边
        if (visited.contains(node)) return false;

        visited.add(node);
        stack.add(node);
        for (T neighbor : graph.successors(node)) {
            if (dfs(neighbor, graph, visited, stack)) {
                return true;
            }
        }
        stack.remove(node);
        return false;
    }

    /**
     * 返回拓扑排序（若有环则抛出异常）
     */
    public static <T> List<T> topologicalSort(Graph<T> graph) {
        if (hasCycle(graph)) {
            throw new IllegalStateException("Graph contains a cycle, cannot topologically sort");
        }

        Set<T> visited = new HashSet<>();
        Deque<T> stack = new ArrayDeque<>();
        for (T node : graph.nodes()) {
            topoDfs(node, graph, visited, stack);
        }
        List<T> result = new ArrayList<>(stack);
        Collections.reverse(result);
        return result;
    }

    private static <T> void topoDfs(T node, Graph<T> graph, Set<T> visited, Deque<T> stack) {
        if (visited.add(node)) {
            for (T neighbor : graph.successors(node)) {
                topoDfs(neighbor, graph, visited, stack);
            }
            stack.push(node);
        }
    }
}
